#include <bits/stdc++.h>

using namespace std;

// 给你正整数 low ，high 和 k 。
// 如果一个数满足以下两个条件，那么它是 美丽的 ：
// 偶数数位的数目与奇数数位的数目相同。
// 这个整数可以被 k 整除。
// 请你返回范围 [low, high] 中美丽整数的数目。
// 测试链接：https://leetcode.cn/problems/number-of-beautiful-integers-in-the-range/
// 帖子讲解：https://leetcode.cn/problems/number-of-beautiful-integers-in-the-range/solutions/2396206/shu-wei-dppythonjavacgo-by-endlesscheng-4gvw/

class Solution 
{
public:
    int numberOfBeautifulIntegers(int low, int high, int k) 
    {
        return cnt(high, k) - cnt(low - 1, k);
    }

    int cnt(int num, int k)
    {
        auto s = to_string(num);
        int n = s.size(), dp[n][k + 1][2 * n + 1];
        memset(dp, -1, sizeof dp);
        /*
        已经构造的数位，模 k 等于 val。根据取模的原则，当我们在第 i 位填入数字 d 后，
        将 val 更新为 (val*10+d) % k在递归终点，判断是否满足 val=0
        
        diff 表示奇数数位的数目与偶数数位的数目的差。在递归终点，判断是否满足 diff=0
        。注意我们无需对奇数数位的数目和偶数数位的数目分别各用一个参数表示，那样效率更低。
        假设填入的数字是 ddd，那么将 diff 加上 (d % 2) * 2 - 1，对应着奇数加一，偶数减一。
        */
        function<int(int, int, int, bool, bool)> f = [&](int i, int val, int diff, bool is_limit, bool is_num) -> int
        {
            if(i == n) return is_num && val == 0 && diff == n;
            if(!is_limit && is_num && dp[i][val][diff] != -1) return dp[i][val][diff];

            int ans = 0;
            if(!is_num) ans = f(i + 1, val, diff, false, false);
            // 如果前面填的数字都和 high 的一样，那么这一位至多填数字 s[i]（否则就超过 high 啦）
            int up = is_limit ? s[i] - '0' : 9;
            for(int d = 1 - is_num; d <= up; ++d) // 枚举要填入的数字 d
            {
                ans += f(i + 1, (10 * val + d) % k, diff + (d % 2) * 2 - 1, is_limit && d == up, true);
            }
            if(!is_limit && is_num) dp[i][val][diff] = ans;
            return ans;
        };

        return f(0, 0, n, true, false);
    }
};